import java.util.ArrayList;
import java.util.List;

public class Solution1020 {
    public int numEnclaves(int[][] grid) {
        int[] dx={-1,0};
        int[] dy={0,-1};
        int m=grid.length,n=grid[0].length;
        int[] b=new int[m*n+1];
        for (int i=0;i<=m*n;i++){
            b[i]=i;
        }
        for (int i=0;i<m;i++){
            for (int j=0;j<n;j++){
                if (grid[i][j]==1){
                    if (i==0 || i==m-1 || j==0 || j==n-1){
                        int x=find(b,i*n+j);
                        int y=find(b,m*n);
                        if (x!=y){
                            b[x]=y;
                        }
                    }
                    for (int k=0;k<2;k++){
                        if (valid(i+dx[k],j+dy[k],m,n) && grid[i+dx[k]][j+dy[k]]==1) {
                            int x=find(b,i*n+j);
                            int y=find(b,(i+dx[k])*n+j+dy[k]);
                            if (x!=y) {
                                b[x]=y;
                            }
                        }
                    }
                }
            }
        }
        int ans=0;
        int target=find(b,m*n);
        for (int i=0;i<m;i++){
            for (int j=0;j<n;j++){
                if (grid[i][j]==1){
                    if (find(b,i*n+j)!=target){
                        ans++;
                    }
                }
            }
        }
        return ans;
    }

    int find(int[] b,int t){
        List<Integer> list=new ArrayList<>();
        while (t!=b[t]){
            list.add(t);
            t=b[t];
        }
        for (Integer integer : list) {
            b[integer]=t;
        }
        return t;
    }

    boolean valid(int x,int y,int m,int n){
        return x>=0 && y>=0 && x<m && y<n;
    }


    public static void main(String[] args) {
        System.out.println(new Solution1020().numEnclaves(new int[][]{{0,0,0,0},{1,0,1,0},{0,1,1,0},{0,0,0,0}}));
    }
}
